<!DOCTYPE html>
<html lang="zh-CN">

<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
    <link rel="shortcut icon" href="">
    <title>递归分割</title>
    <style type="text/css">
        body {
            background-color: #eccc68;
        }

        canvas {
            width: 400px;
            height: 300px;
            border: 1px solid black;
        }
    </style>
</head>

<body>
    <h1>递归分割</h1>
    <script type="module">
        // import * as TWO from './two.js'
        import { Scene, Render, Rect, PickContrls, Vector2 } from './two/two.js'
        // import Point from './two.js'
        // import Render from './two.js'
        const LOG = 0
        const width = 400, height = 300, edge = 20
        let cols = ~~((width * 2) / edge) - 1, rows = ~~((height * 2) / edge) - 1

        let render = new Render()
        render.setSize(width, height)
        render.setPixelRatio(2)
        render.setAnimationLoop(animation)
        document.querySelector('body').appendChild(render.domElement)

        const scene = new Scene()
        const colorMap = {
            0: 'hsl(220, 20%, 50%)', // 路
            1: 'hsl(120, 100%, 50%)', // 墙
            2: 'rgba(250, 177, 160,1.0)', // 起点
            3: 'rgba(255, 118, 117,1.0)',  // 终点
            4: 'hsl(40, 100%, 50%)', // 路线
            5: 'hsl(20, 80%, 50%)', // openList
            6: 'hsl(10, 80%, 50%)', // closeList
        }
        // scene.add(rect)
        // 0-路, 1-墙, 2-待选
        let map = new Array()
        for (let x = 0; x < cols; ++x) {
            map[x] = new Array()
            for (let y = 0; y < rows; ++y) {
                map[x][y] = 0
                const rect = new Rect(edge - 3, edge - 3)
                rect.setAttribute('stroke', false)
                rect.position.copy({ x: (x + 1) * edge, y: (y + 1) * edge })
                scene.add(rect)
            }
        }
        for (let x = 0; x < cols; ++x) {
            map[x][0] = 1
            map[x][rows - 1] = 1
        }
        for (let y = 0; y < rows; ++y) {
            map[0][y] = 1
            map[cols -1][y] = 1
        }

        /*
        const controls = new PickContrls(scene, render.domElement)
        controls.setPixelRatio(2)
        */
        // let x_b = ~~(Math.random() * (cols - 1)) + 1, y_b = ~~(Math.random() * (rows - 1)) + 1
        // map[x_b][y_b] = 0
        clip(1, 1, cols - 2, rows - 2)
        let beg = {x: 1, y: 3}
        let end = {x: 13, y:  3}
        map[beg.x][beg.y] = 0
        map[beg.x + 1][beg.y] = 0
        map[end.x][end.y] = 0
        map[end.x - 1][end.y] = 0
        searchRoad(beg.x, beg.y, end.x, end.y)
        function animation() {
            render.render(scene)

            display()
        }

        function clip(x1, y1, x2, y2) {
            if (x2 - x1 < 2 || y2 - y1 < 2) return
            let x = x1 + 1
            let y = y1 + 1
            if (x2 - x1 >= 3) {
                x = x1 + 1 + ~~(Math.random() * (x2 - x1 - 2))
            }
            if (y2 - y1 >= 3) {
                y = y1 + 1 + ~~(Math.random() * (y2 - y1 - 2))
            }
            x = ~~(x / 2) * 2
            y = ~~(y / 2) * 2
            LOG && console.log('-->' + x1 + ", " + y1 + " | " + x2 + ", " + y2 + " | " + x + ", " + y)
            for (let i = x1; i <= x2; ++i) map[i][y] = 1
            for (let i = y1; i <= y2; ++i) map[x][i] = 1

            /*
            */
            clip(x1, y1, x - 1, y - 1)
            clip(x + 1, y1, x2, y - 1)
            clip(x1, y + 1, x - 1, y2)
            clip(x + 1, y + 1, x2, y2)

            /*

            */
            let r = [0, 0, 0, 0]
            r[~~(Math.random() * 3) ] = 1
            for (let i = 0; i < 4; ++i) {
                if (r[i] === 0) {
                    let rx = x, ry = y
                    switch(i) {
                        case 0:
                            do {
                                rx = x1 + ~~(Math.random() * (x - x1))
                            } while(map[rx-1][ry] + map[rx+1][ry] + map[rx][ry-1] + map[rx][ry+1] > 2)
                            break
                        case 1:
                            do {
                                ry = y1 + ~~(Math.random() * (y - y1))
                            } while(map[rx-1][ry] + map[rx+1][ry] + map[rx][ry-1] + map[rx][ry+1] > 2)
                            break
                        case 2:
                            do {
                                rx = x + 1 + ~~(Math.random() * (x2 - x))
                            } while(map[rx-1][ry] + map[rx+1][ry] + map[rx][ry-1] + map[rx][ry+1] > 2)
                            break
                        case 3:
                            do {
                                ry = y + 1 + ~~(Math.random() * (y2 - y))
                            } while(map[rx-1][ry] + map[rx+1][ry] + map[rx][ry-1] + map[rx][ry+1] > 2)
                            break
                    }
                    map[rx][ry] = 0
                }
            }
        }

        function searchRoad(start_x, start_y, end_x, end_y){
            map[start_x][start_y] = 2
            map[end_x][end_y] = 3
            let closeList = []
            let openList = [{x: start_x, y: start_y, G: 0}]
            console.log(start_x, start_y, end_x, end_y)
            let i = 0;

            while (existList({x: end_x, y: end_y}, openList) < 0 && i++ < 1000) {
                if (openList.length > 0) {
                    let currentPoint = openList.pop()
                    closeList.push(currentPoint)
                    let surrounds = surround(currentPoint)
                    for (let i in surrounds) {
                        let item = surrounds[i]
                        if (item.x >= 0 && item.y >= 0
                            && item.x < cols && item.y < rows
                            && map[item.x][item.y] !== 1
                            && existList(item, closeList) < 0
                            && map[item.x][currentPoint.y] !== 1
                            && map[currentPoint.x][item.y] !== 1
                        ) {
                            let g = currentPoint.G + ((currentPoint.x - item.x) * (currentPoint.y - item.y) === 0 ? 10 : 14)
                            // let g = currentPoint.G + 10
                            if (existList(item, openList) < 0) {
                                item['H'] = (Math.abs(item.x - end_x) + Math.abs(item.y - end_y))  * 10
                                item['G'] = g
                                item['F'] = g + item.H
                                item['parent'] = currentPoint
                                // console.log(JSON.stringify(item))
                                openList.push(item)
                            } else {
                                let index = existList(item, openList)
                                // console.log(JSON.stringify(openList[index]), g)
                                if (g < openList[index].G) {
                                    openList[index].parent = currentPoint
                                    openList[index].G = g
                                    openList[index].F = openList[index].H + g
                                }
                            }
                        }
                    }
                }
                openList.sort((a, b)=> {return b.F - a.F})
                // openList = [openList.pop()]
                // console.log("result: " + JSON.stringify(openList))
            }
            let index = existList({x: end_x, y: end_y}, openList)
            let currentPoint =  openList[index]
            let result = []
            while(currentPoint) {
                result.unshift({x: currentPoint.x, y: currentPoint.y, G: currentPoint.G})
                currentPoint = currentPoint.parent
            }
            console.log(result)
            for (let i = 1, l = result.length - 1; i < l; ++i) {
                map[result[i].x][result[i].y] = 4
            }
        }

        //判断点是否存在在列表中，是的话返回的是序列号
        function existList(point, list) {
            for(var i in list) {
                if(point.x==list[i].x && point.y==list[i].y) {
                    return i;
                }
            }
            return -1;
        }

        function surround(pos={x: 0, y: 0}) {
            let x = pos.x, y = pos.y
            return [
                {x: x - 1, y: y - 1},
                {x: x, y: y - 1},
                {x: x + 1, y: y - 1},
                {x: x - 1, y: y},
                {x: x + 1, y: y},
                {x: x - 1, y: y + 1},
                {x: x, y: y - 1},
                {x: x + 1, y: y + 1}
            ]
        }

        function display() {
            let index = 0
            for (let x = 0; x < cols; ++x) {
                for (let y = 0; y < rows; ++y) {
                    const rect = scene.children[index++]
                    rect.setAttribute('fillStyle', colorMap[map[x][y]])
                }
            }
        }

    </script>

    <code style="width: 800px; height: 250px">
        <p>递归切割算法</p>
        <p>首先假设迷宫全是路，在里面画四面墙，把迷宫分割成四个新区域</p>
        <p>随机选择三面墙打通，这时原本隔开的四个区域又被打通了</p>
        <p>以此类推，在四个新区域内继续设墙分割区域，然后把墙打通，直到不能继续分割才结束</p>
        <a href="https://blog.csdn.net/jjwwwww/article/details/82901326">随机迷宫生成算法——递归分割算法</a>
    </code>
</body>

</html>